# ---
# title: 481. Magical String
# id: problem481
# author: Indigo
# date: 2021-02-03
# difficulty: Medium
# categories: 
# link: <https://leetcode.com/problems/magical-string/description/>
# hidden: true
# ---
# 
# A magical string **S** consists of only '1' and '2' and obeys the following
# rules:
# 
# The string **S** is magical because concatenating the number of contiguous
# occurrences of characters '1' and '2' generates the string **S** itself.
# 
# The first few elements of string **S** is the following: **S** =
# "1221121221221121122……"
# 
# If we group the consecutive '1's and '2's in **S** , it will be:
# 
# 1 22 11 2 1 22 1 22 11 2 11 22 ......
# 
# and the occurrences of '1's or '2's in each group are:
# 
# 1 2 2 1 1 2 1 2 2 1 2 2 ......
# 
# You can see that the occurrence sequence above is the **S** itself.
# 
# Given an integer N as input, return the number of '1's in the first N number
# in the magical string **S**.
# 
# **Note:** N will not exceed 100,000.
# 
# **Example 1:**  
# 
#     
#     
#     Input: 6
#     Output: 3
#     Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.
#     
# 
# 
## @lc code=start
using LeetCode

function magical_string(n::Int)
    res = "122"
    idx = 2
    while length(res) < n
        res *= '1'^(res[idx+=1] - '0')
        res *= '2'^(res[idx += 1] - '0')
    end
    return count(==('1'), SubString(res, 1, n))
end
## @lc code=end
